分布式事务原理

要谈分布式事务，我们就要首先来谈一下本地事务。

事务

本地事务主要要满足四个特性：ACID 。

• Atomic: 原子性
• Consistency: 一致性
• Isolation: 隔离性
• Duration: 持久性

其他几个性质都还比较好理解，主要是我们来讲一下我们有关与隔离性，MySQL是允许多个事务并发操作相同的数据，都有自己的完整数据空间。各个事务之间的操作是隔离的。并发执行的各个事务之间互不干扰。

以上四种本地事务可以见 小林Coding 中MySQL对于几种特性的保证实现原理。我觉得算是设计的比较妙的。

既然说到了的话，我们还是提一下吧。
在 MySQL 中,：

• 持久性由 redo log重做日志保证
• 原子性是undo log 回滚日志保证
• 隔离性是由MVCC多版本并发控制保证的。

MySQL 事务隔离级别

其中MySQL 默认事务隔离级别是：可重复读， 需要注意的是隔离级别越高，所读的数据越准确，但是相应的并发性能越低。

三种问题释义:

• 脏读: 指的是读到了其他未提交事务修改的数据，未提交意味着这些数据可能会回滚.
• 不可重复读： 我个人感觉挺挺这个和上一个挺难分辨的，但是不可重复读的点在于对于重复， 也就是一次事务中重复读取的数据不一致。
  • 可以是A事务读取第一次之后，B事务提交修改了其中的部分数据导致第二次数据读取与第一次事务
• 幻读： 在一个事务内多次查询某个符合查询条件的「记录数量」，如果出现前后两次查询到的记录数量不一样

因此本地事务的保证主要就是靠MySQL的日志来保证的，因为MVCC也比较依靠redo log 和 undo log.

分布式事务

分布式事务主要有几种情况：

• 分库分表（垂直水平拆分）
• 跨库事务
  • 一个应用要操作较多的库， 不同的哭存储不同业务数据。
• 微服物化
  • 将一个系统解耦成多个小部分，每个小部分有自己数据库，业务之间调用通过rpc

并且上文中我们说本地数据库事务需要做到ACID，四个特性。而针对与分布式业务主要就有两个原则: CAP与BASE.

因此我们也在这里引入一下CAP和BASE。

CAP:

• Consistency: 数据的一致性，在CAP一般要求的是在系统中强一致性也就是即时一致性。
• Availability: 可用性，探讨集群中部分节点故障之后整个系统中是否还是可用的。主要体现就是节点挂了之后用户还是可以在一定时间内获取到请求结果。
• Partition tolerance: 分区容错性，分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性或可用性的服务。

而BASE， 则是由CAP演化而来，核心思想就是无法做到强一致性， 但是可以做到最终一致性。

• Basically Available: 基本可用是指分布式系统在出现不可预知的故障的时候，允许损失部分可用性，但不等于系统不可用。
• Soft state: 软状态, 主要允许系统中存在数据中间状态，并认为该中间状态的存在不会影响系统的整体可用性。允许系统不同节点之间同步存在延时。
• Eventually consistent: 系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。就是不需要保证实时强一致性。分为以下几种：
  • 因果一致性：进程A在更新完数据后通知进程B，那么之后进程B对该项数据的范围都是进程A更新后的最新值
  • 读己之所写：进程A更新一项数据后，它自己总是能访问到自己更新过的最新值。
  • 会话一致性： 将数据一致性框定在会话当中，在一个会话当中实现读己之所写的一致性。即执行更新后，客户端在同一个会话中始终能读到该项数据的最新值。
  • 单调读一致性： 如果一个进程从系统中读取出一个数据项的某个值后，那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。
  • 单调写一致性: 一个系统需要保证来自同一个进程的写操作被顺序执行。

因此我们其实能从上面看出来：BASE是靠牺牲一致性获得可用性

XA

XA 是 X/Open 定义的分布式事务处理规范。

主要将全局角色分为：

• AP: Application，应用程序。也就是业务层。
• TM: Transaction Manager，事务管理器。 负责统筹规划全局事务，管理事务状态，协调RM
• RM: Resource Manager，资源管理器。一般是数据库,或者其他资源如 MQ.

XA规范定义了 TM和RM之间接口，形成一个桥梁。主要提出在上个世纪 90 年代，然后在各个数据保证ACID。

XA保持的 Consistency 是 强一致性的， 因此可以把它归为刚性事务。在这个过中会用一个锁所著，TM从prepare到commit、rollback 一直持有。若要修改数据就要等待释放，问题在于长事务风险！

综上来讲，XA协议其实就不是比较适合目前主流的互联网分布式服务了。

XA 的实现

XA 是一个协议，而2PC、3PC、AT等等都是这种刚性事务的具体实现。

其中Seata的AT其实就是 2PCPlus版本。

在2PC (Two-Phase Commit: 两阶段提交)中主要存在两个角色：

• Coordinator 协调者： 其实就是事务管理器
• Participant 参与者: 资源管理器

而他的两个阶段主要是，提交事务请求和事务提交or中断事务。

1. 提交事务请求
   1. 事务询问：协调者向所有参与者发送事务内容，询问是否可以执行提交操作，并开始等待各参与者进行响应
   2. 执行事务：各参与者节点，执行事务操作，并将Undo和Redo操作计入本机事务日志
   3. 各个参与者向协调者反馈事务询问的响应。
2. 执行事务提交or中断事务

只有当所有子事务全部都reply yes之后，这个事务才正常提交。所有其他情况都会发生事务中断这一操作。

就是很直白的靠本地事务完成整个事务。好处就是直白。
XA-两阶段提交协议（以2PC为参考）中会遇到的一些问题:

• 性能问题
• 协调者单点故障问题
• 丢失消息导致的数据不一致问题
• 过于保守

TCC

TCC(Try-Confirm-Cancel) 相较于XA模型不需要RM对于分布式事务的支持，而是对业务逻辑分解。因此TCC有较强的侵入性。

步骤：

• 初步操作 Try：完成所有业务检查，预留必须的业务资源。
• 确认操作 Confirm：真正执行的业务逻辑，不作任何业务检查，只使用 Try 阶段预留的业务资源。因此，只要 Try 操作成功，Confirm 必须能成功。另外，Confirm 操作需满足幂等性，保证一笔分布式事务有且只能成功一次。
• 取消操作 Cancel：释放 Try 阶段预留的业务资源。同样的，Cancel 操作也需要满足幂等性。

TCC 中会添加事务日志，如果 Confirm 或者 Cancel 阶段出错，则会进行重试，所以这两个阶段需要支持幂等；如果重试失败，则需要人工介入进行恢复和处理等。

TCC其实本质和2PC是差不多的：

• T就是Try，两个C分别是Confirm和Cancel。
• Try就是尝试，请求链路中每个参与者依次执行Try逻辑，如果都成功，就再执行Confirm逻辑，如果有失败，就执行Cancel逻辑。

不同的是：

• XA是资源层面的分布式事务，强一致性，在两阶段提交的整个过程中，一直会持有资源的锁。基于数据库锁实现，需要数据库支持XA协议，由于在执行事务的全程都需要对相关数据加锁，一般高并发性能会比较差
• TCC是业务层面的分布式事务，最终一致性，不会一直持有资源的锁，性能较好。但是对微服务的侵入性强，微服务的每个事务都必须实现try、confirm、cancel等3个方法，开发成本高，今后维护改造的成本也高为了达到事务的一致性要求，try、confirm、cancel接口必须实现幂等性操作由于事务管理器要记录事务日志，必定会损耗一定的性能，并使得整个TCC事务时间拉长

因此TCC实际上就是最为复杂的一种情况，处理业务上要尽量避免这种该类事务。一般对于金融、付款类业务使用这种比较好。

SAGA长事务模型

主要由三部分组成:

• LLT (Long Live Transication): 由一个个本地事务组成事务链
• 本地事务: 事务链由一个个子事务组成，LLT = T1 + T2 + T3 + … +Ti
• 补偿：每个本地事务Ti存在对应的补偿Ci

按照正常话来说的话就是，把一个长的事务拆分成为不同的子任务。对于一般的任务，会有一个事务失败对应的回滚操作。

而SAGA 的执行顺序也有两种:

• T1, T2 , T3 …, Tj : 必须要成功的场景，因此不需要Ci
• T1, T2 , T3, …, Tj , Cj, … , C2 ,C1 其中0 < j < n

我们举一个简单的例子一个充值事务:
T1 : VIP 数据插入userId
T2：修改余额 +5
C2: 修改余额 -5
C1: VIP 移除数据 userId。

[!NOTE]

1. Ti 和 Ci是幂等的
   1. 假设在执行Ti的时候超时了，此时我们是不知道执行结果的，如果采用forward recovery策略就会再次发送Ti，那么就有可能出现Ti被执行了两次，所以要求Ti幂等。如果采用backward recovery策略就会发送Ci，而如果Ci也超时了，就会尝试再次发送Ci，那么就有可能出现Ci被执行两次，所以要求Ci幂等。
2. Ci是必须可以成功的，如果无法成功需要人工介入
   1. 如果Ci不能执行成功就意味着整个Saga无法完全撤销
3. Ti - Ci和Ci - Ti的执行结果必须是一样的：sub-transaction被撤销了

因此SAGA主要针对的是长事务并且并且对于及时一致性的要求较低。

资料参考:
https://www.cnblogs.com/crazymakercircle/p/13917517.html#autoid-h3-6-0-2
https://xiaolincoding.com/
https://blog.csdn.net/weixin_37604985/article/details/127469987

0x01 前言

！有很多话是在半夜和酒后写的，浅看当个乐子吧。

想写这篇文章的想法萌生于8月份，只是觉得要对于这二十年做一个小小的总结吧。二十年说长还是挺长的，但是感觉自己二十年来做出来的成绩是比较小的。因此这也并不是一篇夸耀自己的文章，只是从现在出发对于在以前一些的事情的看法。

我不是一个擅长记录的人，因此我所能找到的记录其实是比较少的。当然也只能从这里面的记录里讲讲了。但是从高中到大学这段时间里记录的东西是变多了，记录的对象有我自己也有我的朋友。

说想写但是一直不知道该怎么区分我想说的东西呢，索性就按照过去、现在、将来来划分吧。

0x02 过去

我始终觉得小学到中学时期里，最开心的一段时间是在初中在安徽那边读书的时候。那段时间里跟大家相处比较好，大家也没有什么小心思之类的就聚在一起玩。很可惜之后也因为在初二时候转回四川所以联系也就越来越少了。当然这也是很正常的，因为毕竟不在同一个环境里了，大家聊的东西也不是同一个了。

对于转回来的中学这段时间我没什么好说的。有些人让我感到厌烦可以说到了讨厌的地步。

当然还是有早恋的情况的，也是在初三末期了。后面断断续续也到了高中毕业，也就随之断了。这里面有太多事情了，后面也发生太多事情了。我讲不清但是。后来听说她对我是负面评价，说实话还是挺惊讶的因为我俩最后也算得上她对我的和平分手了吧，我不了解她后面对我的不满来自于回忆中的哪一个部分。好像大多人都把前任当作死对头提到就是破口大骂，我不太理解为什么这样，至少我自己心里有杆秤就行了。还是挺感谢这个姐的，至少给我上了较为重要的一节课吧，首先就是两个人在一起的付出应当是对等的。这个姐们我就一句话吧——她没在我生日的时候说过一句 Happy Birthday 吧 。以至于重塑了我对于谈恋爱这件事情的一些看法。

高中阶段还是很不错的，至少跟初中比起来。越写越觉得有些初中的人是有点病的，暂时先不想了。高中我想想高中三年是怎么过的呢，大概可以用浑浑噩噩来说吧，所以最后也就来到了油专了。高中跟我一起浑浑噩噩过来的应该是就是 苟少了

高中我俩也算是食堂战士了。最终他去了西华我来了油专也算是难兄难弟了。他是母单所以也给他放个广告位吧。

然后高三跟着寝室里的花姐、博博子三天天在寝室用那个平板来放放歌，也算是一种难得的一种休息方式了。每天中午必放的就是那个 Let Me Down Slowly，以至于现在有时候一听到这个歌甚至会哼两句。

我说过之前的图片可能稍微少了那么一点，但是好在还是找到了不少的照片。虽然大家高中的时候都看着挺憨的，但是苟少现在也成为一个穿搭达人了，我以为他到大学了之后学摄影是为了拍人像的。结果买了尼康在拍风景图。

在高中印象最为深刻的事应该就是【五子棋事件】了，现在想起都是难以描述。本来高三大小考试考完晚自习都是对答案，用不了多久时间就可以对完了，然后我就跟童杰开始在草稿本上下五子棋了，正好被年纪主任逮了个正着。 然后第二天就是下了一上午的五子棋。感觉有点好笑。

🐻哥可以说是帅的一了，高中想要联系方式的人数不胜数，但是我觉得本人比照片帅的多了。高一的时候看到他第一眼首先是帅、然后就是感觉就是太高冷了，也没有笑容。后面发现熊哥还是太憨了。

高中跟我在同一个高中的还有王歧鑫和三朝老兵贾北祥。王岐鑫算是闷骚类型的，虽然人看着比较老实但是总能语出惊人。大学里参加了学校组织然后认识了现在的 Girlfriend， 说来惭愧第一次跟她女朋友见面我就拉肚子了别人还送了奶茶。贾北祥是一个多元化的人，怎么说呢这个多元不是大家认为的多元，而是他该日龙的时候日龙（方言，而且总是摇头晃脑的。我个人觉得他的三观跟我是比较契合的。

其实还有好多人没写，我也就不再一一列举了。可以说这个高中还算是比较快乐的，如果我高中能不脑瘫的在高中写书maybe分数更高一点？

高中的时候我们是有平板的，但是平板比较封闭不能玩（虽然当时我找到了方法），最大的作用应该是拿来记录一下生活。但是还是有点可惜我当时没有把所有数据都导出出来。

这寝室进过🐍是真的哈人。

高中毕业之后我其实就比较放开自己了。之后去了趟光雾山玩了一趟，也就是这一趟我觉得我彻底想通了一些事情所以也就不纠缠那位姐了。

倒是意外发现自己的酒量也还行。于是大家也就经常一起约着喝喝酒之类的。附一张成理学子之间的内讧吧：

高中篇就到此结束了。

怎么感觉还写着写着成了回忆录呢捏。

0x03 此时此刻

我是把大一到现在的时间放在了此时此刻里，但是大一到现在也有一两年了说不上是此时此刻。

虽说前文中说的不纠缠那位姐了，但是能一下子缓过来是假的。我会跟另一位朋友说我昨晚梦到她了（虽然听起来很贱，但确实是败犬一条。）我知道我心里当时还是没有死的彻底，但是我也一直告诉我自己我不能再回头了。

大一进入油砖，很有幸遇到了阿堃。阿堃是我的班导，可以说是影响了我大学生活的灵魂人物了。如果没有他的话，可能我还会在寝室每天打着游戏然后玩到大三再跟所有人一样去准备考研。

堃是一个特别优秀的人，从油砖保研到了电子神技大学。我也算追随他的脚步进了Lec。然而中间也算有个小插曲吧就是我没收到面试通知，虽然说云神确实发了，但是我也是真的没有收到。

可以说大学是自由的，和家的距离远了也就是被管控的距离远了。因此还是做了不少之前没有做过的事情比如留了一段时间长头发。但是也因为暑假回家而被正义制裁了。

大一进校的时候正好碰到了寝室楼下的花的盛开。

对于大学的新奇应该只保持了一周左右，和新开学的新鲜感是一样的。然后就是上课、军训，好在军训的时候已经是10月份了。军训的时候天气总是阴的，有时候还会吹起几阵风还会觉得冷。

在大二的上学期，遇到了其他学校的女生。她一开始说加错了，原本相加另外一个的结果不小心加到我这儿了。这倒是我第一次听说的理由，我当然反问了很多次但是每次都是一样的回答，我也就自然信了。于是和所有俗套的剧情一样频繁的聊天产生了不一样的情愫。后来啊，我才知道她话里充斥了太多的谎言。可以说跟她在一起的部分时光是真的快乐的，

但是对于她交际的分寸和谎言也是令我较为不满的点，当然分别有更深层次的原因。我是一个自私的人，如果我不喜欢她了，我会慢慢地想静静地等，等到我的所有的热情都消耗殆尽了。我从来都是一个决绝的人，无论是对之前那位姐还是这位。我知道有些事情不能也不会挽回，所以我会删除一切念想。但是与之前不同的是，在那位姐那儿我多少是学到了点东西的。如今看来也是进行了有效的运用的。至少不会像之前一样要死要活的了。

我越来越觉得记录别人时刻，反而比记住一些自己的事更有意思。自己的事情无非会在自己的记忆里保留，如果是能遗忘的证明也不是那么的重要了。倒是有时候记录他们的时刻翻到时还是会觉得有意思点，但也不是说绝对的对于我自己的不记录。

上面这两张是我觉得拍的最好的几张了，并不是因为色彩、构图什么的了只是纯粹的记录而已里面已经包含了我想要说的话。

我是一个对于服务器这类东西有着接近痴迷的感情的, 因此我在大学里有了自己的第一台实体服务器, 毛逸飞也拍下了我搬运这个的照片，虽然比较糊就是了。

还有去晚上回寝室时候顺路去充电桩给电瓶车充电的李亚文：

以及通宵了之后的早晨：

从文章的前文对比来看就可以知道大学是多了更多照片的。还有很多照片我就不一一列举了，因为记录是列举不完的的，而OSS的容量是有限的、带宽的流出也是付费的。

除此之外，在大学里有幸的是和高中的朋友仍然还没有断。能遇到他们也算是一段幸事。有些时候觉得朋友难以说出口，于是索性称作兄弟吧。于是就会有喝完一堆酒说爬就爬的山，登上山顶等待日出然后就是呕吐。


也会在老家的街头随便逛逛：

这些都称的上算是不错的事情。

可以说，我的大学大部分时间是荒废了的。看到堃、千、泽熙等等还是会有止不住的羡慕的。自己虽然拿到了一些小奖但是始终觉得也就那样吧。但是自己本来也就是这种人了，总是能找的折中的路好像能不上不下的。目前觉得就连保持不上不下也很难了。

大三上该准备考研的开始着手考研了，准备实习的也已经开始了。Java后端好像还是死路一条，看不到什么光明。为了给团队招新去参选了23级班导生，说是为了团队招新其实更多是想把堃给我们说的传递给下一届吧。我自己内心中是这样想的。

0x04 自我总结

跟很多内向的人差不多，我大多时候也是独处的。干自己的事情多一点，倒是进入大学之后感觉内向的感觉消退一点了。由内向转为了假的外向，为什么不是那么社恐了？我个人感觉是因为大学的事情太多了，有时候会忘记为什么要害怕这件事情。

我的性格上我感觉也是改变了一点点吧，在之前我是有点讨好型人格在那儿的。有点太注重于别人怎么想的了，倒是现在不喜欢就不喜欢了，别人看不惯就看不惯了，我看不惯就直接开骂了。爱联系不联系的这种状态了。我觉得这种是真的挺舒服的，至少对于自己来说是真的舒服多了。

我始终是一个彻头彻底的悲观主义者，我会把好多事情的预期度降到很低。因此不会担心哪些人、哪些事情会让我过多的失望。也算是一种精神胜利法，地下道老鼠的自我安慰。毕竟让自己获得开心点还是有好处的。

但是完成的不太好的是读书，书读的太少了有关文学方面的。在手机上之前还会想看看《1984》。说来惭愧这本书在手机上躺了应该也有三四个月左右了，但是始终没有读完，不得不说确实是一部好的小说。自己还是太容易分心了。自己之后这个情况还得改改，人是需要读书的，多读些文学类的书记。历史和语文如果不是应试教育里的课程我应该是很喜欢这两门课的。

我觉得自己算做的好的部分呢，拿到了一些小成绩（只是对我自己而言。除此之外的事情也不再过多的自夸了。

我看我自己形容我自己应该可以说是白开水。 是指我这个人的白开水，我这个人的内在的白开水。我是一个无趣的人，我对很多事情都没有兴趣。有些时候都会以有事情忙为由来推脱掉，因为它本身就是透明的并且是寡淡的。在和所有的人交往过程中我好像都是如此。这里的交往是指一切的人与人之间联系的交往。感觉正因为内心的寡淡，所以感觉有些关系更不会长久。

写到这儿也有三四千左右的字了，我不想写多了怕整个文章拉得过长又害怕自己有些东西写漏了。最后还是先来收个尾吧。最后总是还要谈到自己的感情的，我现在看法就是以前看的最重要的东西反而变成了最不重要的了，还是要谢谢两位了。这种事情开始让我觉得变得浪费时间、没有意义。

然后就是有关以后，说实话是无尽头的迷茫。不知道之后的路会不会很通畅，Java后端的路本来就已经破烂不堪了。我不清楚之后会去哪个公司、哪个城市，我也不知之后会租住在哪个房间，更不知道之后会定居在哪儿。我家里想让我尽量呆在成都，这种强烈的想法反而让我抛弃了成都这个选择。或许是杭州、深圳或者北京。也不是我去选择公司，而是跟大多数人一样让公司去选择我。

在团队里看过太多厉害的人，有学长学姐也有自己同届的。看的越多反而觉得自己的未来越渺茫。

我只能在当前的日子里期待未来越过越好。

整数集合部分

Redis 整数集合(intset), 我通篇读下来之后最大感受其实对于存放数据的操作。

Redis 整数集合的本质其实也是一个数组，只不过里面存放的数据是按照顺序存放的，并且不会重复。

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct intset {

    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];

} intset;

老生常谈的问题是 int8_t 虽然是作为保存元素的数组存在。但是实际上是由encoding的值决定的。

主要有下面三个选项：

• INTSET_ENC_INT16
• INTSET_ENC_INT32
• INTSET_ENC_INT64

当一个数据是一个16位的整数类型的时候，其实我们就可以用两个字节的空间去表示一个元素。
例如一个INTSET_ENC_INT16 可以用两个 int8_t来表示，同理32、64也是以这种方式表示的。

升级

Redis 整数集合比较优秀的一个功能的。比方说我们目前存的数据都是int8类型的整数（虽然redis是16起步的），我用来举例子。我们 就可以使用int8 来正常存储数据。

但是，当插入到一个16位的整数的时候，我们需要对于Redis的整数集合进行升级。从int8->int16 怎么升级呢？

很简单用两个int8 表示一个int16.

那么我们假设原来有 3 个数据:

如上图所示变化.

虽然redis实现了底层数据的升级，但是并没有实现底层数据的降级。

压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。

主要在列表键只包含少量列表项，并且列表项是小整数或者短字符串就会用压缩列表。

压缩列表的节点可以保存来了： 整数值或字节数组。

字节数组的类型：

• length <= 63 Bytes
• length <= 168383 Bytes
• length <= 4294967295 Bytes

整数的类型：

• 4bit (0~12)
• 1Byte Signed
• 3Byte Signed
• int16_t
• int32_t
• int64_t

而一个压缩列表的格式是如下的：

• zlbytes-uint32_t: 整个压缩列表的占用的空间
  • 在内存重新分配时计算zllen会使用到
• zltail-uint32_t: 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节， 是一个偏移量的值
• zllen-uint16_t: 整个列表节点的数量
• entryX-列表节点长度不定
• zlend-uint8_t: | 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

举个例子：

• 列表 zlbytes 属性的值为 0xd2 （十进制 210）， 表示压缩列表的总长为 210 字节。
• 列表 zltail 属性的值为 0xb3 （十进制 179）， 这表示如果我们有一个指向压缩列表起始地址的指针 p ， 那么只要用指针 p 加上偏移量 179 ， 就可以计算出表尾节点 entry5 的地址。
• 列表 zllen 属性的值为 0x5 （十进制 5）， 表示压缩列表包含五个节点。

压缩列表节点

• previouse_entry_length: 记录上一个节点占用的字节长度, 长度为 1byte or 5 byte。
  • 可以通过指针运算利用当前节点起始地址，得到上一个节点的起始地址
  • 这也是如何从表尾遍历到表头的——指针运算
• encodeing: 记录content的数据类型和长度
  • 1 Byte\2Byte\5Byte 最高为00、01、10的为字节数组
    • 字节数组长度就是去除最高位两位数字之后的值
  • 1Byte 且 最高位为11开头的是整数编码, 整数值的类型和长度由编码除去最高两位之后的其他位记录

表格来自: RedisBook

• content：就是实际存储数据的地方。

连锁更新的性能

上面我们列举了 previous_entry_length 可以是一字节 可以是五字节。

因此倘若，我们现在有10个节点的大小都是250～252之间的话，那么我们在redis内部就会选择使用 1字节的长度来表示前一个节点的大小。

当此时，我们在头部插入一个 >= 254 Bytes 的节点的时候，原来的一号节点就会因为1Byte无法表示更高的数字，所以升级成5Bytes。从而导致 node2 表示node1时候也无法用一字节表示，需要升级到五字节。…. 诱发一些列的连锁反应。

这就是我们所要说的连锁更新。因此每次连锁更新的最坏复杂度为 O(N), 最多执行N次空间重分配所以综合下来的最坏复杂度为O(N^2)。

不仅仅是添加节点会导致连锁更新，删除节点同样会导致连锁更新如下图：

若small节点是 < 254字节的，所以e1节点是可以通过一个字节表示small的。但是删去small节点之后，e1 需要用5字节表示big节点。

面试与匆忙的准备

在七月半的时候，有幸得到了一次面试的机会。面试我的人就是我后面的老大——变哥。变哥是电子科大的本硕，我对于变哥的学校光环还是很大的，当然这也是我后面吹水才知道的。

面试时变哥给我的第一印象是一个比较斯文的理工科男生，为什么说男生呢。虽然变哥已经结婚了，但是感觉看着还是十分年轻的。变哥没有问我很多的八股问题，或者说干脆没有怎么涉猎八股，基本上是从我简历上的项目出发的。我简历上所写的项目，是我自己构思、实现再到微服务改造的，因此对于技术的细节上来说我还是比较熟悉的。

可能也正是因为项目上整体回答的还不错，所以进展还是比较顺利的。从周一面试完，周二拿到了HR发来的Offer。整个流程是走的比较快的。只能说这次实习纯粹是意料之外的经历，算得上是无心插柳柳成荫了。因为答应了HR当周报道，因此我也只花了两天的时间去找房子搬东西。

租房的时间实际上过于紧凑了，因此踩了不少坑。首先就是被一个傻逼骗到了一个地方，但是房源信息是假的，中介说经常有人散播虚假的房源信息然后欺骗找找房者前来增加热度。当天的雨下的很大，从地铁站出来之后也被淋湿了不少。早上没有吃任何东西，在旁边的便利店匆忙吃了点东西。我当时的心里是极度愤怒的，但是还是保持了冷静。因为前一天晚上提前找到了很多中介，所以找了另一个马上就前往了下一个地点。看着房子没有太大问题就懒得走了，匆忙签了租房合同。

那一周都是匆忙的，匆忙的面试、匆忙的租房、匆忙的搬运、匆忙的报道。雨天和来回的车程消耗了我对于实习的过多期待。

实习中的经历

进入公司之后，熊姐给我讲了相关的公司福利待遇，兴怡姐给我拿了一台Macbook Pro作为后续工作的电脑。首先的第一感受还是新奇吧，因为第一次进入公司实习，对于好多事情都还不是非常的熟悉。变哥、思雨姐、峰哥跟我打了招呼。然后就是熟悉公司的开发流程。其实按理说这个时间可以拉长一点的，但是我还是比较快的搞好了。无非就是公司的飞书、开发账号权限、私有化GIT权限、sre发布权限之类的。

这里面还是有很多之前没有用过的，比方说的GitLab + Jenkins 的CI/CD。 这是我觉得最方便的东西，虽然感觉打包的还是有点慢，但是提交之后的自动化流程也是真的十分方便了。然后就是阅读一些我们部门仓库的一些代码。

峰哥说我进入的流程还是比较快，因为他当时还是玩了一段时间的，而我在进入公司没多久之后，就开始接开发需求了。第一个需求是为类似于GPT项目增添付费功能，也就是增加VIP会员。非VIP有对话次数限制，然后在微信小程序平台上线付费功能。这是之前从没有做过的功能，其实主要就是对接微信支付的接口。

这里也就是我在开放上的第一课了，首先就是对于功能的过度开发，没有结合相关的引用场景。其中一个方面主要体现在对于超时订单的关闭，因为参考了大多数技术论坛和博客的文章。因此想在这个阶段引入RabbitMq 做一个延时队列。但是公司中的其他项目中其实并没有用到RabbitMq, 因此为这个项目引入RabbitMq其实是不值得的。

首先第一点因素是因为这个项目并非公司的核心盈利项目、第二点是这个项目付费用户其实应该不会有很多。因此我在给变哥讲述了我的理解之后变哥给我分析了一下业务的现状。因此我就考虑从定时任务出发了，定时扫描超时未关闭的订单那。

还有就是第二个项目是关于资源调度的，这个是一个全新的项目。可以说这个也可以作为之后实习找工作的时候的一个资本吧。能从这个项目里发散出来很多新的东西。比如节点信息的一致性如何保证的，与一般的网关有什么不同等等。这个项目应该说是我收获最多的东西。

其实写这两个东西的时候，都有一个问题就是无法在本地完成测试。都需要发布在测试环境之后去验证程序的正确。这个其实一个比较考验编码的地方。

在实习的这一段时间里，也没有迟到过，反而经常是公司来的最早的一批人吧。因为我们公司是9-10点然后晚上的6-7点。我比较看中下班之后的我自己的时间，所以也就选择了早起。这是一个我比较自豪的一点半，能够坚持下来。

有关离职

因为上周五公司组织了团建，在团建时才发现了实习生离职需要提前三天提起申请正好周五的团建也没办法走离职流程。因此我只能先提交离职审批，以此期望在周一的时候能够打满三天吧。

周一这天我有三门课，都以这个理由请假请掉了。因此我早上7:30从学校做到了天府三街。这是我最难忘的一天了，因为这是我第一次做早高峰的一号线。地铁上人贴人前胸贴后背，中间等待了多辆地铁才成功挤上去，好消息是就连离职的最后一天我也是最早的一批来公司的。

在团建上我提前告知了变哥我要离职的消息，但是没有告诉思雨姐。离职的上午变哥问我有没有什么感受，我想了想从变哥这儿学到的一些东西吧。、

1. 对于业务的合理把握，以业务场景与业务量去决定所使用的技术以及开发方向。不要做无谓的过度设计。
2. 对于方法的复用等等
3. …..

其实更多是自己在开发细节上没有考虑到的一个东西。比方说在处理繁忙队列时，直接将其从SuriveSet中移除了，而没有new Set(),addAll() 。 导致了后面的一些小Bug。

变哥最后问了我是否之后有再加入公司的想法，他说如果有这个想法的话可以联系他。这是我觉得我最感动的一个点吧。

下午交接完了所有工作，交出电子设备清除所有数据。就这样从两个月的公司里离职了，说实话还是有点舍不得。我觉得变哥、思雨姐等等都是很好的人呢。

前言

Redis 在跳表中主要应用在 ZSET 中，通常的Zset中的score 就是作为节点排序的依据。

说起跳表可能还是比较陌生，我们会先从SkipList 是什么讲起。

跳表

首先，SkipList 本质是对一个有序数组建立的多层索引的结构。这个数据结构基本上没有在专业相关的教科书中提及过。 因此还是比较新的一种数据结构。

普通的一个链表，如果我们要查找一个其中的一个元素的话。需要遍历整个的链表，因此时间复杂度为 O(n), 如果说是有序的数组的话就我们可以用有二分算法，实现O(logN). 这也是为什么调表有时候会被拿来与二分比较。

这两者的区别就是，链表不支持随机读，数组可以通过下标直接定位读取数据。

说起来有点抽象，但是我们先看图就好了。

如果我们此时定位 元素5 的话， 我们先从第二级索引出发，发现 1 < 5 < 7, 因此我们要从第二级索引中的 1节点下来到第一级索引。 发现 4 < 5 < 7。 重复上面这一个动作找的了5.

因此，这是一种常见的用空间换时间的算法逻辑，通过建立对于元素节点的索引来减少查询需要小的时间。

跳表索引的操作

首先一条链表建立合理的索引，应该使得索引的作用达到最优。

目前普遍的索引建立，晋升的机会应该是1/2。例如 第二级索引之间与第一级索引之间间隔了一个。

其实本质上也是一种二分的思想。

跳表作为一种数据结构，他是支持节点的添加与删除的。那么如果我们在添加与删除操作时不对索引操作会产生什么影响呢？

如果不操作，就会导致一层索引之间包含了过多的节点，退化为一个普通的链表。因此在这种情况下我们只能重建索引来完成这个操作。

由于我们晋升的机会是1/2, 通过我们学习的概率学来说，要保持这个1/2之一的话，我们可以让添加节点时用概率来保证他的晋升机会——需不需要为这个新增节点添加索引而抛硬币。

删除节点是需要把索引信息也删除掉。

Redis 中的跳表

Redis 跳表由 zskiplist, zskiplistnode 两个结构组成， 分别是跳表和跳跃表节点。

1
2
3
4
5
6
7
8
9
10
11
12
13

typedef struct zskiplist {

    // 表头节点和表尾节点
    //指向头和尾
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

• header ：指向跳跃表的表头节点。
• tail ：指向跳跃表的表尾节点。
• level ：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
• length ：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

zskiplistNode 结构， 该结构包含以下属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

typedef struct zskiplistNode {

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

• 层（level）：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层，每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。
  • level数组，在每次创建新的 zskiplistnode节点时，会随机生成一个 1～32值作为数组大小。
  • 层的数量越高访问速度越快
  • level数组作用已经规定了这个节点的最高层次。
  • 前进节点是当前层级节点的下一个节点指针
• 后退（backward）指针：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
  • 后退节点是在针对节点的， 前进节点是针对层的索引的。
  • 后退节点都是连接的上一个真正的节点。
• 分值（score）：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
  • score 是一个 double 的类型的数据 按从小到大排序
• 成员对象（obj）：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。
  • 成员对象指向一个字符串对象，字符串对象保存着一个SDS.
  • 在同一个跳跃表中， 各个节点保存的成员对象必须是唯一的， 但是多个节点保存的分值却可以是相同的。
  • 分值相同的节点将按照成员对象在字典序中的大小来进行排序。
  •  成员对象较小的节点会排在前面， 而成员对象较大的节点则会排在后面。

前言与闲聊

Redis 是一个 Key-Value 的非关系形态的数据库。
字典，就是Redis中保存键值对的抽象数据结构。Key应当是独一无二的。

1
2
3
4
5
6
7
8

redis> HGETALL website
1)"Redis"
2)"Redis.io"
3)"MariaDB"
4)"MariaDB.org"
5)"MongoDB"
6)"MongoDB.org"
# ...

上面的website键就包含了很多键值对， Redis->Redis.io .

Redis 在不少地方都使用了字典并且选择了自己去实现了字典，那么下面就让我们详细的来看一下实现的技术细节吧。

实现细节

哈希表

哈希表用起来是非常舒适的，就像HashMap一样。这种结构可以很好的，存储一些对象类型的数据.

例如我们可以把一个多层级的不定的JSON数据给转换成Map<\String, Object>. 能够更方便我们去动态解析我们所需要的数据。而不用去新建一个Class， 然后去接受对象。

在Redis实现的过程中，主要由两部分 : dictht 和 dictEntry 分别是哈希表和哈希表节点。

下面是Redis 哈希表一种哈希冲突的现象，之后会讲，我们目前只是先看一下大概的结构。

dict.h/dictht

1
2
3
4
5
6
7
8
9
10
11
12
13

typdef struct dictht{
	// 哈希表数组
	dictEntry **table;

	//哈希表大小
	unsigned long size;

	//sizemask = size - 1 用来计算哈希值
	unsigned long sizemask;

	//哈希表已有节点
	unsigned long used;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

值的一提的是，通过C语言的union可以存放 指针、64位带符号或不带符号的长整型的Value。

回到我们刚刚说的哈希冲突现象，可以看到直接将冲突的对象通过拉链法来解决冲突。

将冲突的对象通过链表连接起来，这里展开讲讲Hash冲突三种解决方法也不错:

• 拉链法： 当出现哈希冲突时，也就是说不同的Key存在了相同的哈希值
  • 这样我们就会将冲突的节点组成一个链表，但是极端情况下会变成链表比如全部都哈希冲突
  • JDK 1.8 中HashMap，ConcurrentHashMap 用了都说好
• 再哈希：Key1 发生哈希冲突, hash(hash(key1)) …. -> 依次这样直到不冲突
  • 这种会使得散列更加均匀，但是计算时间长多了
• 开放寻址法：当Key1 这个值发生哈希冲突之后，再次利用这个哈希函数对Key1产生不同的哈希

我们举例子：Hi=（H（key）+d_i）% m   i=1，2，…，n

H是哈希函数，Hi是最终哈希值，d_i是增量序列,m 为哈希表的长度。根据取值的方式不同，再散列方式也不一样。

1. 线性再散列: d_i i=1，2，3，…，m-1
   • 冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表
2. 二次探测再散列: d_i = 1², -1², 2² , -2², ….. , k², -k² (k <= m/2)
   • 冲突发生时，在表的左右进行跳跃式探测，比较灵活。
3. 随机序列： 就取随机数，建立一个随机数序列

字典 dict

字典事实上将 哈希表包了一层：

在字典中有两个 dictht 主要是在哈希表扩容和缩容的时候转移时使用的。在一般情况下只会使用 ht[0]。ht[1] 会在rehash时候用到。

通过上述结构，字典定义了type与privdata，type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的。

dict.h/dict

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

typedef struct dictType {

    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);

    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);

    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);

    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);

    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);

} dictType;

type 指针指向dictType, 因此我们可以针对不同类型的键值对进行操作。

privdata 就会保存一些对应的参数，必要时传给函数。

哈希过程

Redis 是会先将 Key的值进行hash， 然后将得到的hash值与sizemask做与运算，放置到对应的空间里.

1
2
3
4
5
6
7
8

//通过dict类型中包含的特殊函数来hash
hash = dict -> type -> hashcode(key)


# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

经过这两步骤我们得到 index 之后，然后放置在相对应的空间里面。

Rehash 与渐进式Rehash

Rehash 主要发生在Redis 对于字典的哈希表扩展与收缩时候。

什么时候发生扩展和收缩？

我们首先要明白负载因子计算公式：

$$ load_factor = ht[0].used \div ht[0].size$$
这样的得到的 loadfactor 若：

• *扩展
  1. 后台没有BGSAVE、BGREWRITEAOF 命令宾且哈希表负载因子 >= 1
  2. 存在上述两个后台但是负载因子 >= 5
• 收缩
  1. 哈希表的负载因子小于 0.1

而在 BGSAVE、BGREWRITEAOF 是会创建子进程的，由于操作系统的 CopyOnWrite 这个特性会优化效率所以提高了负载因子

那我们如何进行rehash呢？

1. 为ht[1] 开辟空间，空间大小取决于要执行的操作， 以及 ht[0] 当前包含的键值对数量 （也即是 ht[0].used 属性的值）：
   • 如果是扩展， 那么 ht[1] 的大小为第一个>= ht[0].used * 2 的 2^n （2 的 n 次方幂）
     • 举例子 ht[0] 的used为4, 4 * 2 = 8 =< 2 ³ ,因此8 是第一个大于等于ht[0].used * 2的2的n次方幂
   • 如果是收缩， 那么 ht[1] 的大小为第一个>= ht[0].used 的 2^n 。
2. 把ht[0] 键值对重新计算Key的哈希值和索引值, 然后放到ht[1]中
3. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备。

渐进式 Rehash 的应用场景

主要是如果 ht[0] 中的键值对过多的话，就会导致一次性无法转移完成。

为了避免rehash对服务器造成产生过多性能影响， 我们就会采取 渐进式的rehash.

1. 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
2. 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
3. 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
4. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

rehashidx 是用来跟踪当前迁移进度的，表示rehash的哈希槽位的索引值。

Collection 内的亲密关系

老九献给威虎山的先遣图：

上面列举了详细的 Java 集合类框架。

其中主要是两部分分别位于 java.util 和 java.util.concurrent 包中的。

从名字上就可以看到区分的点了：

• java.util.concurrent: 可以保证在并发情况下的对于集合内的修改的安全性。
• java.util: 不一定能保证线程安全性。

并不意味着所有的java.util 下的集合都不能保证线程安全。

其中就有我们今天主要要讲的 Vector 、HashTable 。

Vector

你只要学习过一段时间或者写过一段时间C++(写算法题). 就肯定知道有个东西也叫 vector.

这两个在用法上非常相似，但是我们现在不是聊用法的时候。我们是要深入底层去学习。

组成部分——我来组成头！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
     * The array buffer into which the components of the vector are
     * stored. The capacity of the vector is the length of this array buffer,
     * and is at least large enough to contain all the vector's elements.
     *
     * <p>Any array elements following the last element in the Vector are null.
     *
     * @serial
     */
    protected Object[] elementData;

    /**
     * The number of valid components in this {@code Vector} object.
     * Components {@code elementData[0]} through
     * {@code elementData[elementCount-1]} are the actual items.
     *
     * @serial
     */
    protected int elementCount;

    /**
     * The amount by which the capacity of the vector is automatically
     * incremented when its size becomes greater than its capacity.  If
     * the capacity increment is less than or equal to zero, the capacity
     * of the vector is doubled each time it needs to grow.
     *
     * @serial
     */
    protected int capacityIncrement;

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = -2767605614048989439L;

上面的注释已经给出了部分信息，即Vector本质是一个 Object数组。这是一个按照顺序插入的一个数组，元素最后一个之后的数组都是空的。

并且，Vector的容量是自动扩大的。在每次Vector大小大于容量时候，向量每次增长时并且 capacityIncrenment <= 0 的时候容量都会加倍。

被创建的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public Vector(int initialCapacity, int capacityIncrement) {
	super();
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal Capacity: "+
										   initialCapacity);
	this.elementData = new Object[initialCapacity];
	this.capacityIncrement = capacityIncrement;
}

public Vector(int initialCapacity) {
	this(initialCapacity, 0);
}


public Vector() {
	this(10);
}


public Vector(Collection<? extends E> c) {
	elementData = c.toArray();
	elementCount = elementData.length;
	// c.toArray might (incorrectly) not return Object[] (see 6260652)
	if (elementData.getClass() != Object[].class)
		elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

Vector 创建时默认传入初始容量、容量增长值。值的注意的是默认情况下容量是10个。增长值为0，因此根据上文我们先推测在遇到增长时，容量会变成20.

Vector 添加移除的过程

我们先来说添加的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public synchronized boolean add(E e) {
	modCount++;
	ensureCapacityHelper(elementCount + 1);
	elementData[elementCount++] = e;
	return true;
}

private void ensureCapacityHelper(int minCapacity) {
	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
									 capacityIncrement : oldCapacity);
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) // overflow
		throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ?
		Integer.MAX_VALUE :
		MAX_ARRAY_SIZE;
}

添加的过程中，首先通过 ensureCapacityHelper 去确定需不需要扩容，让当前容量 > 数组当前的长度的时候就会调用 grow 方法去扩容。

grow 在确定新容量空间时，会在 capacityIncrement <= 0 时直接加上当前数组长度。
因此也印证我们前面的推论。

但是，在得到新的容量空间之后，它还会去判断够不够。够了之后就 System.copyOf 去建立新的数组。

其次就是移除的过程：

移除的过程也有两个操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

public boolean remove(Object o) {
	return removeElement(o);
}

public synchronized boolean removeElement(Object obj) {
	modCount++;
	int i = indexOf(obj);
	if (i >= 0) {
		removeElementAt(i);
		return true;
	}
	return false;
}

public synchronized void removeElementAt(int index) {
	modCount++;
	if (index >= elementCount) {
		throw new ArrayIndexOutOfBoundsException(index + " >= " +
												 elementCount);
	}else if (index < 0) {
		throw new ArrayIndexOutOfBoundsException(index);
	}
	int j = elementCount - index - 1;
	if (j > 0) {
		System.arraycopy(elementData, index + 1, elementData, index, j);
	}
	elementCount--;
	elementData[elementCount] = null; /* to let gc do its work */
}


public synchronized E remove(int index) {
	modCount++;
	if (index >= elementCount)
		throw new ArrayIndexOutOfBoundsException(index);
	E oldValue = elementData(index);

	int numMoved = elementCount - index - 1;
	if (numMoved > 0)
		System.arraycopy(elementData, index+1, elementData, index,
						 numMoved);
	elementData[--elementCount] = null; // Let gc do its work

	return oldValue;
}

分别是 remove(Object o) 和 remove(int index).

remove(Object o) 在某种程度和另外一种没有区别。

因为它也是先找到这个object 在哪儿。然后去通过index删除值。

需要注意的是， elementData[–elementCount] = null 这句话，看我们前面的JVM内容中GC是通过可达性分析来判断是否回收的。

因此这么做的目的也是为了在通过System.arraycopy(elementData, index + 1, elementData, index, j) 这样移除掉第index之后，将最后一个重复的元素移除。使得gc可以有效回收。

Vector 一些总结信息

Vector 算是一个比较简单的类，可以自己试着实现一下。

还有你会发先在关键操作中，add、remove中vector都是通过synchronized这个关键字来保证线程安全性。因此在性能是比较孱弱的。

ArrayList在实现上与Vector 是比较相似的。但是ArrayList 通过modCount 实现了快速失败的 效果。

后面也不会再细讲 ArrayList 相关信息。

先上提交的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    var tmp,res *ListNode = head,head
    if k <= 1 {
        return head
    }
    var cap []*ListNode = make([]*ListNode, k+2)
    LOOP:
    for tmp != nil {
        for i:=1; i <= k;i++{
            cap[i] = tmp;
            if tmp.Next != nil || i == k {
                tmp = tmp.Next
            }else{
                cap[0].Next = cap[1]
                break LOOP
            }
        }
        
        if cap[1] == head {
            res = cap[k]
        }

        for i:= k; i>=1;i--{
            if i !=  1{
                cap[i].Next = cap[i-1]
            }else{
                cap[1].Next = nil
                if cap[0] != nil{
                    cap[0].Next = cap[k]
                }
                cap[0] = cap[1]
            }
            
        }
        
    }
    
    return res
}

个人认为这段代码还是过于丑了，只从最简单的方向考虑，就是先开 k+1个数组。

数组从cap[1]开始中存放的是的当前的k个节点的指针。cap[0]是上一组的最后一个节点，用来连接下一组。

其次我们从后往前更换Next就好了。

类加载机制

类加载的时机

一个类整个生命周期会有7个阶段：加载(Loading)、验证(Verification)、准备(Preparation)、解析(Resolution) 、初始化(Initialization)、使用(Using)、卸载(unloading)

这几个阶段中，加载、验证、解析、初始化、卸载这几个阶段顺序是确定的。类的加载过程都是按照这个顺序开始的， 不是运行、结束，因为这几个过程是会相互交叉混合进行。

而解析阶段有可能会在初始化阶段之后再次开始——支持运行时绑定（动态绑定）的特性。

JVM规范并没有对加载什么时候做规定，但是对于初始化严格规定必须在遇到六种情况下马上执行。

下面初始化阶段前置条件都是还没初始化过。

1. 遇到new、getstatic、putstatic、invokestatic这四个指令码时，若没有初始化过就会触发初始化阶段。
   1. new关键字创建对象
   2. 读取设置一个静态字段
   3. 调用一个静态方法
2. java.lang.reflect 包对类型进行反射调用的时候
3. 初始化类发现父类没有初始化过
4. 虚拟机启动用户指定执行的主类
5. JDK7 java.lang.MethodHandle 实例最后解析结果为 REF_getStatic、REF_p utStatic、REF_invokeStatic、REF_newInvokeSpecial 这几种方法句柄。
6. 接口定义了JDK8新加入的默认方法（被default关键字修饰的接口方法），其实现类被初始化时，接口要先于实现类初始化

JVM规范规定 有且仅有 流中场景才会触发初始化。
上面六种方式称为主动引用，其他不会触发初始化的引用是被动引用。

比方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public A {
	static{
		sout("A");
	}
	public static int a = 123;
}

public B extend A{
	static{
		sout("B");	
	}
}

public test{
	psvm{
		sout(B.a);
	}
}

这种情况下会输出：

1
2

A
123

只有直接定义这个字段的类会被初始化，因此通过其子类来引用父类中定义的静态字段，只会触发 父类的初始化而不会触发子类的初始化。

子类会不会被初始化没有做出明确的规定，这点取决于虚拟机的具体实现。

列二：

1
2
3
4
5

public class test{
	psvm{
		A[] arr = new A[10];
	}
}

这种情况下也是不会触发输出“A”这个操作，因为这个实际上的字节码时 newarray. 会初始化一个[Lorg.fenixsoft.classloading.A 这个类，这个里是由虚拟机自动生成的继承自Object的类。

例三

1
2
3
4
5
6
7
8
9
10
11
12

class ConstantClass{
	static{
		sout("hello world");
	}
	public static final String nihao = "hello";
}

public class Test{
	psvm{
		sout(ConstantClass.nihao);
	}
}

这种情况下，nihao是一个常量，会位于常量池中。经过常量传播优化会存储在Test常量池中。

Loading

Loading is a part of Class Loading.
加载是类加载的一个部分。

有三个步骤:

1. 通过全限定名取类的二进制字节流。
2. 将字节流代表的静态存储结构转化为方法区的运行时数据结构。
3. 在内存中生成一个代表这个类的java.lang.Class 对象，作为方法区这个类的各种数据的访问入口。

JVM规定三条不严格导致之后，从各个地方读取Class：

• zip, Jar, war
• 网络中获取
• 运行时计算生成，使 用 得 最 多 的 就 是 动 态 代 理 技 术 ，在 java.lang.reflect.Proxy 中 ， 就 是 用 了 ProxyGenerator.generateProxyClass( ) 来 为 特 定 接 口 生 成 形 式 为 “ *$Proxy ” 的代理类的二进制字节流 。
• …..

非数组类型加载过程中，我们可以把握操作的地方是：获取类的二进制流这个动作。
可以通过JVM内置引导类加载器、用户自定义类加载器完成（重写 findClass(), 或者 loadClass()）。

数组类型不通过类型加载器创建，由JVM在内存中动态够再出来。但是数组类的元素类型最终还是要依靠JVM来完成加载。

遵循以下规则：

• 如果数组的组件类型(Component Type，指的是数组去掉一个维度的类型 int[] 组建类型是int）是引用类型，那就递归采用本节中定义的加载过程去加载这个组件类型，数组C将被标 识在加载该组件类型的类加载器的类名称空间上。
• 若组建类型不是引用类型，JVM会把数组C标记为与引导类加载器关联
• 数组类可访问性与他的组建类型可访问性一直。若不是引用类型，数组类可访问性默认public

加载阶段与链接阶段部分动作（字节码文件格式验证）交叉进行。

Verification

Verification is first step of Link.
验证是链接的第一步。

这是来确保Class字节流信息符合JVM的规范。

Java是一门相对安全的语言，它不允许操作数组之外的元素、代码行不存在的事。这些会在Class文件编译时被报错出来。但是任有可能会通过hexedit的方式编辑出一个Class来。所以验证十分重要。

验证的步骤：

1. 文件格式验证：
   1. 魔数是不是0xCAFEBABE
   2. 主次版本号能否被接受
   3. 常量池里有没有不可接受的常量类型
   4. ….

这是只是文件校验的冰山一角。

2. 元数据验证：这一个阶段主要是字节码描述进行语义分析

   • 是否有父类（除了Object外都有）
   • 父类是不是继承了不允许被继承的类
   • 是不是抽象类，是否实现父类、接口中要求实现的方法。
   • …..

3. 字节码验证： 验证阶段最复杂的一个阶段，通过数据流分析和控制流分析，确定程序语义是否合法、是否符合逻辑。

   • 保证任意时刻操作数栈的数据类型与指令的代码序列都可以配合工作。不会放了一个int类型，按照long类型载入本地变量表
   • 保证任意跳转指令不会跳转到方法体以外的字节码指令上。
   • 保证方法体类类型转换都是有效的。
   • …..

我们只能通过这个检查我们写的东西有没有Error不能检测出有没有Bug。

在JDK 6之后的Javac编译器和Java虚拟机里进行了一项联合优化，把尽可能 多的校验辅助措施挪到Javac编译器里进行。具体做法是给方法体Code属性的属性表中新增加了一项名 为“StackMapTable”的新属性。

因此我们可以直接检查StackMapTable里的记录是否合法。

4. 符号引用验证： 这一步骤发生在虚拟机将符号引用转化为直接引用的时候, 这个转化动作将会在链接的第三阶段解释阶段发生。

• 符号引用通过字符串的全限定名是否能找到类
• 子啊制定类中是否存在符合方法的字段描述及简单名称描述的方法和字段。
• 符号引用中的类、字段、方法的可访问性是否可以被当前类访问。

这个阶段不是必须的，如果这个程序运行的全部代码已经被反复使用验证过可以通过 -Xverify: none 关闭类验证。

Preparation

准备阶段会为类中定义的变量分配内存并设置初始值。

• 只会分配类变量，不包括实例变量。 实例变量是在实例化时随对象一起分配在Java堆中。

上面时通常情况下是 0， 当类字段存在常量属性如final的话，那在准备阶段就会被初始化为常量。

Resolution

解析阶段是将常量池内的符号引用替换为直接引用的过程。

• 符号引用(Symbolic References): 一组无歧义的符号描述引用的目标。与JVM实现的内存布局无关，引用目标不一定是已经加载到JVM中的内容。
• 直接引用(Direct References): 可以直接指向目标的指针、相对偏移量或者一个能间接定位的目标句柄。这个是与JVM实现的内存布局相关的，引用的对象是肯定存在在JVM内存中的。

JVM规范没有要求解析发生的时间段，但是在执行ane-warray、checkcast、getfield、getstatic、instanceof、invokedynamic、invokeinterface、invoke-special、invokestatic、invokevirtual、ldc、ldc_w、ldc2_w、multianewarray、new、putfield和putstatic这17个用于操作符号引用的字节码指令之前，先对它们所使用的符号引用进行解析。

对于方法或者字段的访问也会在解析时候检查他们的可访问性。

同时对于同一个符号引用进行多次解析请求也是比较常见的，一个符号如果多次被引用那么第一次被引用成功那么后续也应该成功。同理如果第一次失败了，后续也会受到同样异常。

但是！ invokedynamic指令不适用这个规则，碰到某个由inovkedynamic的指令触发解析的符号引用时，会对第一次使用的结果缓存。 这样的引用就是动态调用点限定符。

“动态”是指指令必须等到程序实际运行到这儿时解析动作才能正常运行。

解析动作主要针对类或接口、字段、类方法、接口方法、方法类型、方法句柄和调用点限定符这7类符号引用进行。

类或者接口的解析

当前代码类为D, 若要一个未解析过的符号引用N解析为一个类或者接口C的直接引用, 有三个步骤：

1. 若c不是数组类型，JVM会把代表N的全限定名传递给D的类加载器去加载C.
   • 由于元数据检验等有可能触发其他类的加载，一个错误都不行。
2. 若c是数组类型，并且元素类型为对象。也就是N描述符为类似 “[Ljava/lang/Integer” 的形式。按照第一点规则加载
3. 若上面没出错就可以认为一个有效的类或者接口了。但是还要确定是否符合访问权限。

JDK9 模块化之后嗨哟确定模块间访问权限。

字段解析

要解析一个从未被解析过的字段符号引用，要先对字段表内class_index项中的索引的CONSTANT_Class_info 符号进行解析。

会对字段所属的类或接口符号引用，若出现了任何错误，都会失败。

那把这个字段所属的类或接口用C表示，《Java虚拟机规范》要求按照如下步骤对C进行后续字段的搜索：

1）如果C本身就包含了简单名称和字段描述符都与目标相匹配的字段，则返回这个字段的直接引用，查找结束。

2）否则，如果在C中实现了接口，将会按照继承关系从下往上递归搜索各个接口和它的父接口，如果接口中包含了简单名称和字段描述符都与目标相匹配的字段，则返回这个字段的直接引用，查找结束。

3）否则，如果C不是java.lang.Object的话，将会按照继承关系从下往上递归搜索其父类，如果在父类中包含了简单名称和字段描述符都与目标相匹配的字段，则返回这个字段的直接引用，查找结束。

4. 否则查找失败，抛出java.lang.NoSuchFieldError异常。

方法解析

也需要解析出方法表的 classs_index项中索引的方法所属的类或接口的符号引用。

如果解析成功，我们也要用C表示这个类。按照下面的步骤搜索：

1. Class 文件格式中类方法和接口方法符号引用的常量类型定义分开的。若在class_index 索引中C是个接口就抛异常。
2. 若通过第一部，C中查找似乎否有简单名称与描述符都与目标匹配的方法，有返回这个方法的直接引用然后结束。
3. 否则C父类中递归重复第二步后部分动作
4. 否则在类C实现的列表接口及他们的父接口递归查找，重复第二步后部分。
5. 都最后一步了 失败了

接口方法解析

一样的然后步骤：

1. 如果在接口方法表中发现class_index中的索引C是个类而不是接口，那么就直接抛出异常。
2. 否则，C中查找是否有简单名称和描述符都与目标相匹配的方法，如果有则返回这个方法的直接引用，查找结束。
3. 类似上面的步骤

Initlization

初始化才开始真正执行类中编写的Java程序代码。

在准备阶段变量已经被初始化零值. 在这个阶段会根据程序编码去初始化变量与其他资源。

初始化阶段就是执行 <clinit>() 方法。不是Java直接编写的是Javac自动生成的。

<clinit>() 是编译器自动收集类中的所有赋值动作和static块。顺序是由出现的顺序的决定的。

1
2
3
4
5
6
7

public class Test {
    static {
        i = 0;  //  给变量复制可以正常编译通过
        System.out.print(i);  // 这句编译器会提示“非法向前引用”
    }
    static int i = 1;
}

<clinit>() 与类构造函数不同，不用显式调用父类构造器，JVM需要保证在子类<clinit>() 执行前，父类<clinit>() 就执行好了。因此在Java虚拟机中第一个被执行的<clinit>()方法的类型肯定是java.lang.Object。

注意这个东西不是必须的，如果没有静态代码块或者变量赋值操作，就没有这个方法。

接口不能使用静态方法块但是可以有变量赋值。
JVM必须保证<clinit>()在多线程中正确的加锁同步。如果多个线程执行这个类的<clinit>()，其他线程都要阻塞等待。所以如果其中一个操作耗时过长就会进程阻塞。

例如:

1
2
3
4
5
6
7

class Test{
	static{// 如果不加上这个if语句，编译器将提示“Initializer does not complete normally”并拒绝编译
		if(true){
			while(true){};
		}
	}
}

类与类加载器

类加载器虽然只用于类的加载动作，但是作用远远超过这个。

任意类必须有由加载它的类加载器和他的本身一起确立在JVM中的唯一性。比较两个类是否相等(equals) 、isAssignableFrom()、isInstance() 等方法以及instanceof 这个关键字都是要注意到类加载器的影响。

这两个类来源于同一个Class文件，被同一个Java虚拟机加载，只要加载它们的类加载器不同，那这两个类就必定不相等。

双亲委派机制

在JVM的角度中，只有Bootstrap ClassLoade(启动类加载器 C++ 实现是JVM的一部分)、其他所有类加载器(Java 实现存在于JVM之外 全部继承自ClassLoader)。

但是在使用者角度上来说从JDK1.2之后引入模块化系统之前保持着三层类加载器、双亲委派机制的类加载架构。

下图就是双亲委派模型。

• Bootstrap ClassLoader：主要是加载\lib ，或者被-Xbootclasspath参数指定的路径。它加载主要考文件名识别如: rt.jar
  • 无法被java程序直接引用，若用户自定义编写类加载器需要将加载请求委托给它，就要用null替代。
• Extension ClassLoader: 在类sun.misc.Launcher$ExtClassLoader用Java实现。负责加载\lib\ext 目录中或被java.ext.dirs系统变量制定路径中所有的类库。
  • 允许用户将具有通用性的类库放置在ext目录里以扩展Java SE的功能
• Application ClassLoader: sun.misc.Launcher$AppClassLoader 实现，由于程序类加载器由ClassLoader类中的getSystemClassLoader() 返回的值。
  • 主要负责加载用户类路径Classpath的上的所有类库
  • 若用户自己没有自定义的类加载器，默认情况就是这个加载器。

在双亲委派机制中，除了Bootstrap ClassLoader 外，都要求每个类加载器有自己的父类加载器，不是父类，即不是用继承实现的而是组合。

他不是一个强制性约束条件，是推荐实现的最佳实践。

他是如何加载的：

1. 若一个类加载器收到类加载请求，首先会将请求委派给父类加载器。
2. 所有的请求最终都会传递到顶层的父类加载器完成，当父类加载器无法实现这个加载时。本身才会尝试加载，依次向下。

好处：Java中的类随着它的类加载器一起具备了一种带有优先级的层次关系。

如java.lang.Object 放在rt.jar 那就肯定是被Bootstrap Classloader加载。如果我们去获取他的类加载器就是null。因此Object也能一定保证各种类加载环境都是同一个类。

如果我们尝试用自己的类，来测试我们的类加载器

虽然它非常重要，但是实现比较简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

protected Class<?> loadClass(String name, boolean resolve)
        throws ClassNotFoundException
    {
        synchronized (getClassLoadingLock(name)) {
            // First, check if the class has already been loaded
            Class<?> c = findLoadedClass(name);
            if (c == null) {
                long t0 = System.nanoTime();
                try {
                    if (parent != null) {
                        c = parent.loadClass(name, false);
                    } else {
                        c = findBootstrapClassOrNull(name);
                    }
                } catch (ClassNotFoundException e) {
                    // ClassNotFoundException thrown if class not found
                    // from the non-null parent class loader
                }

                if (c == null) {
                    // If still not found, then invoke findClass in order
                    // to find the class.
                    long t1 = System.nanoTime();
                    c = findClass(name);

                    // this is the defining class loader; record the stats
                    PerfCounter.getParentDelegationTime().addTime(t1 - t0);
                    PerfCounter.getFindClassTime().addElapsedTimeFrom(t1);
                    PerfCounter.getFindClasses().increment();
                }
            }
            if (resolve) {
                resolveClass(c);
            }
            return c;
        }
    }

双亲委派机制的破坏

上面提到了它不是一个强约制性的的模型，所以就可以被破坏。

历史上一共出现过三次被破坏的历史:

1. JDK1.2 之前已经存在的自定义类加载器与双亲委派机制的碰撞

由于为了兼容大部分用户自定义的类加载器，设计者做出了一定量的妥协。所以他们放弃了对于重写loadClass() 方法的可能性转而添加了 findClass方法。当父类加载器失败之后，loadClass方法就会调用 findClass 方法去加载。因此更为推荐重写findClass来实现自己的加载逻辑。

重写findClass()和loadClass() 方法的区别？

• 重写findClass()不会破坏双亲委派模型
• 重写 loadClass() 会破坏双亲委派模型

2. 模型本身缺陷导致
   基础类型会被很多用户代码继承，所以被称之为基础类型。但是也会存在基础类型调用用户代码的情况。

这就是JNDI标准服务，他的目的是对于资源查找和统一管理。需要调用其他厂商实现并部署在应用程序ClassPath下JNDI的SPI代码。但是启动类加载器不认识怎么办？

于是引入了不优雅的线程上下文类加载器(Thread Context ClassLoader)。这个类加载器可以通过可以通过java.lang.Thread类的setContext-ClassLoader()方 法进行设置，如果创建线程时还未设置，它将会从父线程中继承一个，如果在应用程序的全局范围内 都没有设置过的话，那这个类加载器默认就是应用程序类加载器。

3. 用户对程序动态性的追求而导致
   这里就不过多阐述了。

模块的引入

JDK9 提出了模块路径的概念。

简单来说，就是某个类库到底是模块还 是传统的JAR包，只取决于它存放在哪种路径上。只要是放在类路径上的JAR文件，无论其中是否包 含模块化信息(是否包含了module-info.class文件)，它都会被当作传统的JAR包来对待;相应地，只 要放在模块路径上的JAR文件，即使没有使用JM OD后缀，甚至说其中并不包含module-info.class文 件，它也仍然会被当作一个模块来对待。

模块的访问规则：

• JAR文件在类路径的访问规则:所有类路径下的JAR文件及其他资源文件，都被视为自动打包在 一个匿名模块(Unnamed Module)里，这个匿名模块几乎是没有任何隔离的，它可以看到和使用类路 径上所有的包、JDK系统模块中所有的导出包，以及模块路径上所有模块中导出的包。

• 模块在模块路径的访问规则:模块路径下的具名模块(Named Module)只能访问到它依赖定义 中列明依赖的模块和包，匿名模块里所有的内容对具名模块来说都是不可见的，即具名模块看不见传 统JAR包的内容。

• JAR文件在模块路径的访问规则:如果把一个传统的、不包含模块定义的JAR文件放置到模块路 径中，它就会变成一个自动模块(Automatic M odule)。尽管不包含module-info.class，但自动模块将 默认依赖于整个模块路径中的所有模块，因此可以访问到所有模块导出的包，自动模块也默认导出自 己所有的包。

出现模块之后的类加载器

JDK9 没有更改三层类加载器和双亲委派模型只是做出了一些变动。

Extension ClassLoader 被 Platform ClassLoader取代。
既然整个JDK都基于模块化进行构建(原来的rt.jar和tools.jar被拆分 成数十个JM OD文件)，其中的Java类库就已天然地满足了可扩展的需求，那自然无须再保留 \lib\ext目录

其次平台类加载器和应用类加载器都不再派生自 java.net.URLClassLoader. 有程序直接 依赖了这种继承关系，或者依赖了URLClassLoader类的特定方法，那代码很可能会在JDK 9及更高版 本的JDK中崩溃。

之后都全部继承自 jdk.int ernal.loader.Built inClassLoader

JDK9 之前的类加载器：

之后的类加加载器继承关系：

Class 类文件结构

一、前言

一个优秀的程序或系统一般具有良好的兼容性。
比如 Windows11 目前仍然可以运行Windows7 时代的程序。

而我们的JVM也有很好的向后兼容性，这也得益于我们的Class 文件结构的稳定。不同版本的《Java虚拟机规范》对Class文件格式添加，但未更改已经存在的内容。

二、 深入Class文件结构

根据《Java虚拟机规范》的规定，Class文件格式采用一种类似于C语言结构体的伪结构来存储数据，这种伪结构中只有两种数据类型：“无符号数”和“表”。

• 无符号数一般是以 u1、u2、u4、u8表示 一个字节的、两个字节、四字节、8字节的无符号数。
• 表：由多个无符号数或其他表作为数据项构成的复合数据类型。
  • 所有表命名习惯以 _info 结尾, 整个Class文件可以看做一张大的表

那我们的Class表长什么样子呢？如下图

[!NOTE]
在我们不清楚一个数据项有多少个时，我们通常留有一个数字表示他的个数。

Class各个数据项之间没有分隔符，因此所有数据的顺序数量都是被严格限定的，才可以被我们有效的读入。

MagicNumber 与 版本号

魔数(MagicNumber)是一个较为通用且有效的标识符，你可以在很多协议、文件格式中都可以发现魔数的存在。

Class文件的魔数如前文的表中列出的是一个u4的数据。他的作用是确定是否是可以被接受的Class文件。

而在Java中的魔数则是0xCAFEBABE， 也算是一个小彩蛋了。

因此如果你之后有机会制定协议或文件格式，你也不妨试试留一个小彩蛋呢。

在魔数之后的就是Class文件版本号。位于第五六字节的是次版本号（MinorVersion）,七八字节是主版本号（MajorVersion）.

Java 版本号是从 45开始，JDK1.1 之后每个大版本都在主版本号上+1.

• JDK 1.1能支持版本号为45.0～45.65535的Class文件，但不支持46、47之类的版本。

在JDK1.2 到 JDK12 之间从未使用次版本号，JDK12时期开启使用副版本号。

例如笔者上图中的次版本号就是0，无奖竞猜可以猜一下我的JDK版本。

常量池

紧跟着的是常量池入口。常量池是Class文件最大的数据项目之一。

常量池内容是不定的，因此有一个前置的计数(u2 constant_pool_count)，来表示常量池的容量，是从1 开始计数的。

设计者将第0号空出来目的在于，如果后面某些指向常量池的索引值的数据在特定情况下需要表达“不引用任何一个常量池项目”的含义，可以把索引值设置为0来表示。

主要存放两大类常量：

• 字面量（Literal）： 字符串、final常量值
• 符号引用（Symbolic References）
  • package: 被模块导出或开放的包
  • fully qualified name: 类和接口全限定名——org/example/Main
  • Descriptor：字段名称、描述符
  • 方法名称描述符
  • Method Handle, Method Type, Invoke Dynamic
  • 动态调用点和动态常量（Dynamically-Computed Call Site、Dynamically-Computed Constant）

Java代码在Javac编译的Class文件不会保存各个方法、字段最终内存布局信息。这一点是与C/C++ 不同的，它们有“连接”的步骤，Java是在Class在虚拟机加载的时候动态加载.

Java 的常量表是最繁琐的数据：

可以看到每个结尾都是_info， 也就是说每个数据项都是一个表。并且每个数据项之间的关联性确实不大。

这里我就不再详细展开了。

访问标志

繁碎的常量池结束后，就是 u2 access_flag. 她用来表示这个Class时接口还是类， 是否为public、是否为abstract、类的话是不是final, etc.

目前access_flags 一共16位 目前仅使用了9个，剩下的留空可以方便之后拓展。

我们的类是被public修饰，所以只有ACC_PUBLIC , ACC_SUPER 为真因此 0x0001|0x0020 = 0x0021.

类索引、父类索引、接口索引结合。

this_class、super_class两个索引都是u2类型数据，interfaces是一组u2类型数据集合。

Java就是靠Class中的这三个数据确定类型的继承顺序，this_class 制定这个类的全限定名、super_class 制定父类全限定名，Java不允许多类继承，因此出了java.lang.Object外，父类索引都不为0.

字段表集合、方法表集合

字段表（field_info），描述接口或类中申明的变量。 Field 包括类级变量、实例级变量不包括方法内部声明的局部变量。

字段可以包括的修饰符有字段的作用域（public、private、protected修饰符）、是实例变量还是类变量（static修饰符）、可变性（final）、并发可见性（volatile修饰符，是否强制从主内存读写）、可否被序列化（transient修饰符）、字段数据类型（基本类型、对象、数组）、字段名称。

我们可以再深入看到字段访问标识符标记：

在语法的限制下其实有较多的是不能同时选择的。

name_index, descriptor_index 都是对于常量池项的引用。分别是简单名称和方法描述符.

全限定名称在前面已经展示过例子了，而简单名称就是例如一个方法名为 add(), 它的简单名称就是add.

那么接下来我们又谈到方法表集合，方法表集合我们可以根据它的结构来推测。

属性表

attribute_info 在之前出现过多次， Class文件、字段表、方法表都可以携带自己的属性表集合。来描述某些场景的专有信息。

与其他数据项目要求严格顺序、长度、内容不一样，它的限制宽松一点，不要求有严格的顺序。只要不和已有属性名重复就可以了。

每一个属性都要从常量池中引用一个 CONSTANT_Utf8_info 来表示常量表示。属性值结构自己定义。需要一个u4长度的属性去说明属性值占用的位数。

Code 属性

Code属性是最重要的属性之一。
Java程序的方法代码编译后，最后字节码指令就在Code属性内。并不是所有方法都有这个属性，接口就没有。

attribute_name_index 指向了常量code, 表示这个小会难过的名称，attribute_length 则表示属性值的长度。

max_stack 达标了操作数栈(Operand Stack) 深度的最大值，任何操作数不会超过这个深度。

max_locals 局部变量表所需要的存储空间， 单位是Slot. 变量槽是JVM为局部变量分配内存的最小单位。 byte、char 、float等不超过32字节的数据类型每个局部变量占用一个变量槽。而64位的数据类型如double就需要两个slot。

code_length、code 是用来存储Java源程序编译后生成的字节码指令。分别表示字节码长度和存储字节码指令的一系列字节流。

[!WARN]
虽然code_length是u4类型，但是JVM明确限制了一个方法不可以超过65535条字节码指令。

通过 javap -verbose test.class 我们就可以看到里面的字节码

在这里有一个 .<init> 方法，但是没有参数。为什么args_size = 1 、locals = 1?

这是因为每个方法里都可以用this来访问对象本身。

Exceptions 属性

这是与Code平级的属性，他的作用是列举出方法中可能会出现的受查异常(Checked Exceptions) ， 也就是方法 throws 后面跟着的Exception

LineNumberTable属性

这个属性是用来描述Java源码与字节码行号之间的偏移量关系的。不是运行时必要属性。

可以在Javac中使用-g：none或-g：lines选项来取消或要求生成这项信息。如果选择不生成LineNumberTable属性，对程序运行产生的最主要影响就是当抛出异常时，堆栈中将不会显示出错的行号。

…..

剩下的属性不再一一赘述。

字节码

一、前言

这一部分其实如果有学过 计算机系统基础 这门课的同学明白会很快。因为会与反汇编之后的指令很像。

对于大部分数据类型相关的字节码指令中，i对应int的类型操作，l表示long，s是short，b代表byte，c是char，f为float，d肯定就是double，a是reference。

但是也存在没有明确指定操作类型的指令：array length 但是操作数永远只能是一个数组类型对象。

下面是Java虚拟机指令集支持的数据类型。

可以看到大部分指令都是还没支持byte、char、short的，甚至没有指令支持boolean。

编译器会在编译器或运行期将byte与short带符号位拓展为int类型。boolean、char也是零位拓展到int。

[!NOTE]
这一部分我不会细讲，去学习一下 计算机系统基础 这门课程。
我只会列一下各个指令、和必要的提示

各种类型的指令

加载存储指令

加载和存储指令用于将数据在栈帧中的局部变量表和操作数栈。
（真的学了计算机系统基础之后就会很轻易明白我的意思）

下面部分带<>结尾的，其实代表了 iload_0 iload_1…. iload3 这几条指令。
是iload的特殊形式。

• 将一个局部变量加载到操作栈:iload、iload_<n>、lload、lload_<n>、fload、fload_<n>、dload、dload_<n>、aload、aload_<n>

• 将一个数值从操作数栈存储到局部变量表:istore、istore_<n>、lstore、lstore_<n>、fstore、fstore_<n>、dstore、dstore_<n>、astore、astore_<n>

• 将一个常量加载到操作数栈:bipush、sipush、ldc、ldc_w、ldc2_w、aconst_null、iconst_m1、iconst_<i>、lconst_<l>、fconst_<f>、dconst_<d>

• 扩充局部变量表的访问索引的指令:wide

运算指令

·加法指令:iadd、ladd、fadd、dadd
·减法指令:isub、lsub、fsub、dsub
·乘法指令:imul、lmul、fmul、dmul
·除法指令:idiv、ldiv、fdiv、ddiv
·求余指令:irem、lrem、frem、drem
·取反指令:ineg、lneg、fneg、dneg
·位移指令:ishl、ishr、iushr、lshl、lshr、lushr
·按位或指令:ior、lor
·按位与指令:iand、land
·按位异或指令:ixor、lxor ·局部变量自增指令:iinc
·比较指令:dcmp g、dcmp l、fcmp g、fcmp l、lcmp

类型转化指令

小范围转大范围是安全的，因此Java提供了以下指令来处理窄化类型处理：包括i2b、i2c、i2s、l2i、f2i、f2l、d2i、d2l和d2f。这是因为窄化很有可能导致转换结果产生不同正负号、精度丢失等问题。

Java虚拟机将一个浮点值窄化转换为整数类型T(T限于int或long类型之一)的时候，必须遵循以 下转换规则:

• 如果浮点值是NaN，那转换结果就是int或long类型的0。

• 如果浮点值不是无穷大的话，浮点值使用IEEE 754的向零舍入模式取整，获得整数值v。如果v在 目标类型T(int或long)的表示范围之类，那转换结果就是v;否则，将根据v的符号，转换为T所能表 示的最大或者最小正数。

对象创建和访问指令

• 创建类实例的指令:new

• 创建数组的指令:new array 、anew array 、mult ianew array

• 访问类字段(static字段，或者称为类变量)和实例字段(非static字段，或者称为实例变量)的 指令:getfield、putfield、getstatic、putstatic

• 把一个数组元素加载到操作数栈的指令:baload、caload、saload、iaload、laload、faload、 daload、aaload

• 将一个操作数栈的值储存到数组元素中的指令:bastore、castore、sastore、iastore、fastore、 dastore、aastore

• 取数组长度的指令:array lengt h ·检查类实例类型的指令:inst anceof、checkcast

操作数栈管理指令

如同操作一个普通数据结构中的堆栈那样，Java虚拟机提供了一些用于直接操作操作数栈的指
令，包括:

• 将操作数栈的栈顶一个或两个元素出栈:p op 、p op 2
• 复制栈顶一个或两个数值并将复制值或双份的复制值重新压入栈顶:dup 、dup 2、dup _x1、 dup 2_x1、dup _x2、dup 2_x2
• 将栈最顶端的两个数值互换:swap

控制转移指令

控制转移指令可以让Java虚拟机有条件或无条件地从指定位置指令(而不是控制转移指令)的下 一条指令继续执行程序，从概念模型上理解，可以认为控制指令就是在有条件或无条件地修改PC寄存 器的值。控制转移指令包括:

• 条件分支:ifeq、iflt、ifle、ifne、ifgt、ifge、ifnull、ifnonnull、if_icmpeq、if_icmpne、if_icmplt、if_icmpgt、if_icmple、if_icmpge、if_acmpeq和if_acmpne
• 复合条件分支:tableswitch、lookupswitch
• 无条件分支:goto、goto_w、jsr、jsr_w、ret

方法调用和返回指令

• invokevirtual指令:用于调用对象的实例方法，根据对象的实际类型进行分派(虚方法分派)， 这也是Java语言中最常见的方法分派方式。
• invokeinterface指令:用于调用接口方法，它会在运行时搜索一个实现了这个接口方法的对象，找 出适合的方法进行调用。
• invokespecial指令:用于调用一些需要特殊处理的实例方法，包括实例初始化方法、私有方法和 父类方法。
• invokestatic指令:用于调用类静态方法(static方法)。
• invokedy namic指令:用于在运行时动态解析出调用点限定符所引用的方法。并执行该方法。前面 四条调用指令的分派逻辑都固化在Java虚拟机内部，用户无法改变，而invokedy namic指令的分派逻辑 是由用户所设定的引导方法决定的。

异常处理方法

Java显示抛出异常操作(throw语句)都是由athrow指令实现的。

同步指令

JVM 支持方法级别同步与方法内部一段指令序列的同步。都是使用管程（Monitor) 实现的。

方法级别的同步是隐式的，无需字节码控制。虚拟 机可以从方法常量池中的方法表结构中的ACC_SYNCHRONIZED访问标志得知一个方法是否被声明为 同步方法。